The present invention relates to routing in a packet switched network. In particular, it relates to methods of performing session load balancing and reducing polarization effects. In a packet switched network, each incoming packet at a router is sent to an output path, with the choice of output path made based on information at the router. (Where a packet has multiple destinations, it can be routed to multiple output paths.) A divergent network is one in which there are multiple paths going through different routers for at least one source-destination pair.
A packet is said to belong to a session. A session is a unidirectional end-to-end IP communication between two IP nodes. All packets in a session have the same source IP address and the same destination IP address.
A destination IP prefix is a leading part of the destination IP address, typically denoting the network address; e.g., IP address 198.01.01.01 can have a destination IP prefix of 198.01. Destination IP prefixes are commonly used to make routing decisions, as known in the art of routing. For example, a table may be maintained showing possible output paths by destination IP prefix.
At a router, an active path for a packet is a valid route to reach the destination address of the packet, that is deemed to have an acceptable cost, as known in the art of routing. A path can be specified in terms of a next-hop IP address and output interface, as known in the art of routing. Load balancing at a router can be thought of as the ability to share the traffic to a destination IP prefix over all active paths. In this application below, the terms “path” and “active path” are used interchangeably.
It is known to achieve near-perfect traffic sharing using per packet routing, where a round-robin based scheme can be used to load balance each packet, and packets in the same session can follow different paths. However, this can result in packet reordering and non-predictive latency for a session, which are undesirable for some applications. Per session load balancing largely eliminates these disadvantages, as known in the art.
In per session load balancing, all packets from a session take the same path from source to destination. Load balancing at a router is the ability to share the traffic to a destination prefix over all the output paths of a router. That is, for a given destination IP address, load sharing can be implemented by having the same number of sessions assigned to each path active for that destination. In a router one or more active paths to a given destination IP prefix may be assigned to an output interface of that router.
In per session load balancing, packets belonging to a session that arrive at a router must consistently be routed to the path. It is known to accomplish this via a hash function that depends only on the source address and destination address for a given number of active paths, and therefore always gives the same result for a given source and destination pair (“(S,D) pair”). The result is called the hash bin or hash result. The hash bin is mapped to a path. In prior art routers, the same hash function is used in each router of a given model and/or manufacturer of router, as described below.
The hash function is designed to evenly distribute the possible (S,D) pairs among the hash bins. For example, typically there can be 16 hash bins with values that are integers between 0 and 15, inclusive. If there are two paths, 8 of the hash bins will be assigned to the first path and 8 hash bins to the second path. This is typically accomplished by assigning even hash bins, i.e. hash bins in the set {0, 2, 4, 6, 8, 10, 12, 14}, to the first path and odd hash bins to the second path, or vice versa. It is known to achieve uneven load sharing by assigning hash bins proportionally; for example, 3:1 load sharing between two paths can be accomplished by assigning 12 hash bins to one path and 4 hash bins to the second path.
Packet routing is by nature decentralized because packets are routed to a next-hop upon arrival at a router. Fast performance is needed because of increasing network traffic and demands for faster response time. Although prior systems are decentralized and fast, a problem is that systems including such routers implementing per session load balancing are observed to exhibit systematically unequal distribution of load sharing. This is a problem among other reasons because links are not used efficiently.
Accordingly, it would be desirable to perform fast session load balancing that reduces systematic load imbalances presently observed. It would further be desirable if the system were decentralized and fine adjustments in load sharing could easily be achieved without reconfiguring the network topology.